package com.clps.algorithm.chapter07.二叉树最底层最左边的值;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 如何在一个二叉树中找出它最底层中最左边节点的值？假设二叉树中最少有一个节点。例如在图7.5中的二叉树中最底层节点中最左边一个节点的值是5。
 * 图7.5：一棵二叉树，最底层最左边的节点的值是5。
 */
public class demo1 {
    public static void main(String[] args) {

    }

    public  int findBootmleftValue(TreeNode root){
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        int bottomLeft = root.val;
        while (!queue1.isEmpty()){
            TreeNode node = queue1.poll();
            if(node.left!=null){
                queue2.offer(node.left);
            }
            if(node.right!=null){
                queue2.offer(node.right);
            }
            if(queue1.isEmpty()){
                queue1 = queue2;
                queue2 = new LinkedList<>();
                if(!queue1.isEmpty()){
                    bottomLeft = queue1.peek().val;
                }
            }
        }

        return  bottomLeft;
    }
}
